An important part of the development of software systems is testing. Because software systems can involve millions of lines of source code in separate modules or routines which interact, testing is necessary before a system can be shipped, so as to confirm that a given system performs as expected under various configurations and with various inputs. Oftentimes, extensive testing at different development levels, and under a wide variety of testing conditions, helps developers feel confident that the system is unlikely to exhibit unexpected behavior when used by consumers.
Different types of software system testing are used at different stages in development. For example, source code is tested at compile time for syntactic and logical errors before being compiled into executable code. Or, system implementations, either in part or in whole, are tested by users manually affecting inputs and configurations of the system to test against expected outputs. In yet other examples, this testing is automated, using a separate software module or application to automatically run software through batteries of tests.
A challenge in many types of software testing is the creation of representative and meaningful test cases, which are then used in manual or automatic testing of the software itself in order to test the behavior of the software under various operating conditions. Testing a piece of software with different test cases can involve such activities as, for example, varying inputs to a method or making differing function calls.
Unfortunately, development of test cases increases the costs of software testing in such scenarios. The test cases have to be derived somehow, and the test cases have to be run on the software being tested. Running these test cases can be very expensive, because the testing environment for the software might have costs and/or time constraints. For example, a test for mobile phone software could involve establishing a real phone connection.
Oftentimes, to reduce this cost, test cases are grouped into classes according to properties they share. In some scenarios, if every test case in a given class causes a piece of tested software to behave similarly, only one case out of the class of cases is used to verify that the software will behave properly for all inputs that fall into that class. Thus, one challenge is to identify classes from which a small number of test cases can be determined which cover the defined behavior of a program or piece of software.
There are certain disadvantages to testing a method or program on arbitrary input values. Some programs or methods are not defined for every possible input or are only used under specific conditions. A precondition indicates whether a method is defined (or used) for a particular input. If a tester only wants to test software on inputs for which the software is defined and/or used, it is desirable to reduce test cases down to those inputs which satisfy the precondition. Additionally, by carefully reducing the number of test cases, testing may be made more efficient, avoiding testing on cases which are undefined or never used in the software.
Sometimes, however, the process of deciding whether the behavior of a program/method is defined for a given test case is itself described by a complicated precondition program or method. If the precondition program/method is complex, it may substantially increase the difficulty of finding applicable test cases for the program/method being tested. Consider an example where a method m which takes two inputs, a and b, is defined only when the following precondition holds: a and b are relatively prime. Determining if two numbers are relatively prime is the same problem as determining that their greatest common divisor [“GCD”] is 1. Thus, the evaluation of this precondition involves the computation of the GCD. This means that determining test cases for the method m will involve determining which of the test cases have inputs a and b whose GCD is 1. If this GCD method is substantially more complex than m itself, then evaluating the precondition could dramatically increase the costs of finding test cases for m.
What is needed are efficient techniques for finding test cases for a program being tested which satisfy the precondition of the program.